import java.util.*;
import java.util.concurrent.DelayQueue;

public class Solution {
    //1.两个数组的交集 II
    public int[] intersect(int[] nums1, int[] nums2) {
        //交集不用考虑顺序
        //让nums2为长度小的一方，方便创建ret数组
        if(nums1.length > nums2.length){
            return intersect(nums2, nums1);
        }
        int[] ret = new int[nums1.length];
        int retIndex = 0;//ret数组下标
        Map<Integer, Integer> map = new HashMap<>();
        //放入map中并计数
        for(int i = 0; i < nums1.length; i++){
            if(map.containsKey(nums1[i])){
                map.put(nums1[i], map.get(nums1[i]) + 1);
            }else{
                map.put(nums1[i], 1);
            }
        }
        //用nums2进行比较
        for(int i = 0; i < nums2.length; i++){
            if(map.containsKey(nums2[i]) && map.get(nums2[i]) > 0){
                ret[retIndex++] = nums2[i];
                map.put(nums2[i], map.get(nums2[i]) - 1);
            }
        }
        return Arrays.copyOf(ret, retIndex);
    }
    //2.两数之和 II - 输入有序数组(边界双指针)
    public int[] twoSum(int[] numbers, int target) {
        //由于序列有序，所以可以使用边界双指针
        int left = 0;
        int right = numbers.length - 1;
        while(left < right){
            if(numbers[left] + numbers[right] > target){
                right--;
            }else if(numbers[left] + numbers[right] < target){
                left++;
            }else{
                return new int[] {left + 1, right + 1};
            }
        }
        return new int[0];
    }
    //3.剑指 Offer 04. 二维数组中的查找
    public boolean findNumberIn2DArray(int[][] matrix, int target) {
        //对每一行进行二分查找
        for(int i = 0; i < matrix.length; i++){
            int left = 0;
            int right = matrix[0].length - 1;
            while(left <= right){
                int mid = (left + right) / 2;
                if(matrix[i][mid] > target){
                    right = mid - 1;
                }else if(matrix[i][mid] < target){
                    left = mid + 1;
                }else{
                    //找到了
                    return true;
                }
            }
        }
        return false;
    }
    //4.螺旋矩阵(模拟边界)
    public List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> list = new ArrayList<>();
        int len = matrix[0].length;
        int row = matrix.length;
        //模拟边界法
        int left = 0;//左
        int right = len - 1;//右
        int top = 0;//上
        int down = row - 1;//下
        while(left <= right && top <= down){
            //上侧
            for(int i = left; i <= right; i++){
                list.add(matrix[top][i]);
            }
            if(list.size() == len * row){
                break;
            }
            //右侧
            for(int i = top + 1; i <= down; i++){
                list.add(matrix[i][right]);
            }
            //下侧
            for(int i = right - 1; i >= left; i--){
                list.add(matrix[down][i]);
            }
            if(list.size() == len * row){
                break;
            }
            //左侧
            for(int i = down - 1; i > top; i--){
                list.add(matrix[i][left]);
            }
            left++;
            right--;
            top++;
            down--;
        }
        return list;
    }
    //5.颜色分类
    private int fundPoint(int[] nums, int start, int end){
        int key = nums[start];
        while(start < end){
            while(start < end && nums[end] >= key){
                end--;
            }
            nums[start] = nums[end];
            while(start < end && nums[start] <= key){
                start++;
            }
            nums[end] = nums[start];
        }
        nums[start] = key;
        return start;
    }
    private void quick(int[] nums, int left, int right){
        if(left >= right){
            return;
        }
        //找基准
        int point = fundPoint(nums, left, right);
        quick(nums, left, point - 1);
        quick(nums,point + 1, right);
    }
    public void sortColors(int[] nums) {
        quick(nums, 0, nums.length - 1);
    }
    //6.轮转数组(暴力超时)
    public void rotate(int[] nums, int k) {
        //思路：交换思维即可
        for(int i = 0; i < k; i++){
            for(int j = nums.length - 1; j > 0; j--){
                swap(nums, j, j - 1);
            }
        }
    }
    private void swap(int[] nums, int i, int j){
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
    //6.轮转数组(reverse法)
    public void rotate(int[] nums, int k) {
        int len = nums.length;
        while(k > len){
            k -= len;
        }
        //先将整体反转
        int left = 0;
        int right = len - 1;
        reverse(nums, left, right);
        //再将前k个数反转
        left = 0;
        right = k - 1;
        reverse(nums, left, right);
        //将后k个数反转
        left = k;
        right = len - 1;
        reverse(nums, left, right);
    }
    private void reverse(int[] nums, int left, int right){
        while(left < right){
            int tmp = nums[left];
            nums[left] = nums[right];
            nums[right] = tmp;
            left++;
            right--;
        }
    }
    //7.螺旋矩阵 II(模拟边界)
    public int[][] generateMatrix(int n) {
        int[][] ret = new int[n][n];
        //同样的方法，模拟边界
        int left = 0;//左
        int right = n - 1;//右
        int top = 0;//上
        int down = n - 1;//下
        int num = 1;//自然数
        while(left <= right && top <= down){
            //上侧
            for(int i = left; i <= right; i++){
                ret[top][i] = num++;
            }
            if(num - 1 == n * n){
                break;
            }
            //右侧
            for(int i = top + 1; i <= down; i++){
                ret[i][right] = num++;
            }
            //下侧
            for(int i = right - 1; i >= left; i--){
                ret[down][i] = num++;
            }
            if(num - 1 == n * n){
                break;
            }
            //左侧
            for(int i = down - 1; i > top; i--){
                ret[i][left] = num++;
            }
            left++;
            right--;
            down--;
            top++;
        }
        return ret;
    }
    //8.搜索二维矩阵
    public boolean searchMatrix(int[][] matrix, int target) {
        int len = matrix[0].length;
        int high = matrix.length;
        int i = 0;
        //在每一行判断是否在其中
        for(; i < high; i++){
            if(target >= matrix[i][0] && target <= matrix[i][len - 1]){
                break;
            }
        }
        //判断i是否出界，若出界，则说明不存在
        if(i == high){
            return false;
        }
        //对i这一行进行二分查找
        int left = 0;
        int right = len - 1;
        while(left <= right){
            int mid = right + (left - right) / 2;
            if(matrix[i][mid] > target){
                right = mid - 1;
            }else if(matrix[i][mid] < target){
                left = mid + 1;
            }else{
                return true;
            }
        }
        return false;
    }

    public int minSubArrayLen(int target, int[] nums) {
        //滑动窗口
        int len = nums.length;
        int left = 0;//窗口左边界
        int right = 0;//窗口右边界
        int sum = 0;
        int ret = Integer.MAX_VALUE;//要返回的数组长度
        while(right < len){
            sum += nums[right];
            while(sum >= target){
                ret = Math.min(right - left + 1, ret);
                sum -= nums[left++];
            }
            right++;
        }
        if(ret == Integer.MAX_VALUE){
            return 0;
        }else{
            return ret;
        }
    }
    //9.长度最小的子数组(滑动窗口)
    public int minSubArrayLen(int target, int[] nums) {
        //滑动窗口
        int len = nums.length;
        int left = 0;//窗口左边界
        int right = 0;//窗口右边界
        int sum = 0;
        int ret = Integer.MAX_VALUE;//要返回的数组长度
        while(right < len){
            sum += nums[right];
            //sum >= target，就增大left，就可以减小sum；
            //这里不用担心left > right，会减掉原先大于sum的哪个数
            while(sum >= target){
                ret = Math.min(right - left + 1, ret);
                sum -= nums[left++];
            }
            right++;
        }
        if(ret == Integer.MAX_VALUE){
            return 0;
        }else{
            return ret;
        }
    }
    //10.滑动窗口最大值(优先级队列——超时)
    public int[] maxSlidingWindow(int[] nums, int k) {
        //优先级队列,建立大根堆
        PriorityQueue<Integer> queue = new PriorityQueue<>(new Comparator<Integer>(){
            public int compare(Integer o1, Integer o2){
                return o2 - o1;
            }
        });
        int len = nums.length;
        int[] ret = new int[len - k + 1];
        int retIndex = 0;
        for(int i = 0; i < len; i++){
            if(i < k - 1){
                queue.add(nums[i]);
            }else{
                queue.add(nums[i]);
                ret[retIndex++] = queue.peek();
                queue.remove(nums[i - k + 1]);
            }
        }
        return ret;
    }
    //滑动窗口最大值(双端队列)
    public int[] maxSlidingWindow(int[] nums, int k) {
        //双端队列
        //窗口大小为1，就是原数组
        if(k == 1){
            return nums;
        }
        int len = nums.length;
        int[] ret = new int[len - k + 1];
        int retIndex = 0;
        Deque<Integer> deque = new LinkedList<>();
        deque.add(nums[0]);
        for(int i = 1; i < len; i++){
            if(i < k - 1){
                //保持递减队列
                while(!deque.isEmpty() && nums[i] > deque.peekLast()){
                    deque.pollLast();
                }
                deque.addLast(nums[i]);
            }else{
                while(!deque.isEmpty() && nums[i] > deque.peekLast()){
                    deque.pollLast();
                }
                deque.addLast(nums[i]);
                //加入对头
                ret[retIndex++] = deque.peekFirst();
                //判断窗口头是否与队列头相等，若相等将队列头出队
                if(deque.peekFirst() == nums[i - k + 1]){
                    deque.pollFirst();
                }
            }
        }
        return ret;
    }
}
